{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge Operations to Turn Array Into a Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使用合并操作将数组转换为回文序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由&nbsp;<strong>正整数&nbsp;</strong>组成的数组 <code>nums</code>。</p>\n",
    "\n",
    "<p>可以对阵列执行如下操作，<strong>次数不限</strong>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择任意两个&nbsp;<strong>相邻&nbsp;</strong>的元素并用它们的&nbsp;<strong>和</strong>&nbsp;<strong>替换&nbsp;</strong>它们。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>例如，如果 <code>nums = [1,<u>2,3</u>,1]</code>，则可以应用一个操作使其变为 <code>[1,5,1]</code>。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em>将数组转换为&nbsp;<strong>回文序列&nbsp;</strong>所需的&nbsp;<strong>最小&nbsp;</strong>操作数。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,3,2,1,2,3,1]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 我们可以通过以下 2 个操作将数组转换为回文:\n",
    "- 在数组的第 4 和第 5 个元素上应用该操作，nums 将等于 [4,3,2,<strong><u>3</u></strong>,3,1].\n",
    "- 在数组的第 5 和第 6 个元素上应用该操作，nums 将等于 [4,3,2,3,<strong><u>4</u></strong>].\n",
    "数组 [4,3,2,3,4] 是一个回文序列。\n",
    "可以证明，2 是所需的最小操作数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 我们在任意位置进行 3 次运算，最后得到数组 [10]，它是一个回文序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-operations-to-turn-array-into-a-palindrome](https://leetcode.cn/problems/merge-operations-to-turn-array-into-a-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-operations-to-turn-array-into-a-palindrome](https://leetcode.cn/problems/merge-operations-to-turn-array-into-a-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,1,2,3,1]', '[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import Deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        d: Deque[int] = deque(nums)\n",
    "        nOps: int = 0\n",
    "            \n",
    "        while len(d) > 1:\n",
    "            if d[0] == d[-1]:\n",
    "                d.popleft()\n",
    "                d.pop()\n",
    "            elif d[0] < d[-1]:\n",
    "                d.appendleft(d.popleft() + d.popleft())\n",
    "                nOps += 1\n",
    "            else:\n",
    "                d.append(d.pop() + d.pop())\n",
    "                nOps += 1\n",
    "\n",
    "        return nOps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i, j = 0, n-1\n",
    "        left, right = nums[i], nums[j]\n",
    "        res = 0\n",
    "        while i < j:\n",
    "            if left < right:\n",
    "                i += 1\n",
    "                left += nums[i]\n",
    "                res += 1\n",
    "            elif left > right:\n",
    "                j -= 1\n",
    "                right += nums[j]\n",
    "                res += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                left, right = nums[i], nums[j]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre = nums[i]\n",
    "        suf = nums[j]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1 \n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        ans = 0\r\n",
    "        i, j = 0, n - 1\r\n",
    "        pre, suf = nums[0], nums[-1]\r\n",
    "        while i < j:\r\n",
    "            if pre < suf:\r\n",
    "                i += 1\r\n",
    "                pre += nums[i]\r\n",
    "                ans += 1\r\n",
    "            elif pre > suf:\r\n",
    "                j -= 1\r\n",
    "                suf += nums[j]\r\n",
    "                ans += 1\r\n",
    "            else:\r\n",
    "                i += 1\r\n",
    "                j -= 1\r\n",
    "                pre = nums[i]\r\n",
    "                suf = nums[j]\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans\n",
    "    \"\"\"\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        cnt = -2\n",
    "        left, right = 0, len(nums)-1\n",
    "        res = len(nums)-1 if left < right else 0\n",
    "        ls, rs = 0, 0\n",
    "        while left <= right:\n",
    "            if ls <= rs:\n",
    "                ls += nums[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                rs += nums[right]\n",
    "                right -= 1\n",
    "            cnt += 1\n",
    "            if ls == rs:\n",
    "                res = min(res, cnt + self.minimumOperations(nums[left:(1+right)]))\n",
    "        return res\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r =0, n - 1\n",
    "        left, right = nums[l], nums[r]\n",
    "\n",
    "        if n == 1 : return 0\n",
    "\n",
    "        res = 0\n",
    "        while l < r:\n",
    "\n",
    "            if left < right:\n",
    "                l += 1\n",
    "                left += nums[l]\n",
    "                res += 1\n",
    "            \n",
    "            elif left > right:  \n",
    "                r -= 1\n",
    "                right += nums[r]\n",
    "                res += 1\n",
    "\n",
    "            else:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "                left, right = nums[l], nums[r]\n",
    "\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i, j = 0, n - 1\n",
    "        pre, suf = nums[0], nums[-1]\n",
    "        while i < j:\n",
    "            if pre < suf:\n",
    "                i += 1\n",
    "                pre += nums[i]\n",
    "                ans += 1\n",
    "            elif pre > suf:\n",
    "                j -= 1\n",
    "                suf += nums[j]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                pre = nums[i]\n",
    "                suf = nums[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        i = 0 \n",
    "        j = len(nums) - 1\n",
    "        res = 0\n",
    "        while i < j:\n",
    "            left = nums[i]\n",
    "            right = nums[j]\n",
    "            while left != right and i < j:\n",
    "                if left > right:\n",
    "                    j -= 1\n",
    "                    right += nums[j]\n",
    "                    res += 1\n",
    "                elif left < right:\n",
    "                    i += 1\n",
    "                    left += nums[i]\n",
    "                    res += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return res if j >= 0 else len(nums) -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        nums = deque(nums)\n",
    "\n",
    "        ans = 0\n",
    "        while len(nums) > 1:\n",
    "            while len(nums) > 1 and nums[0] != nums[-1]:\n",
    "                if nums[0] > nums[-1]:\n",
    "                    nums.append(nums.pop() + nums.pop())\n",
    "                else:\n",
    "                    nums.appendleft(nums.popleft() + nums.popleft())\n",
    "                ans += 1\n",
    "            \n",
    "            nums.popleft()\n",
    "            if nums:\n",
    "                nums.pop()\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        lf, ri = 0, n - 1\n",
    "        res = 0\n",
    "        while lf < ri:\n",
    "            if nums[lf] == nums[ri]:\n",
    "                lf += 1\n",
    "                ri -= 1\n",
    "                continue\n",
    "\n",
    "            else:\n",
    "                if nums[lf] > nums[ri]:\n",
    "                    nums[ri - 1] += nums[ri]\n",
    "                    ri -= 1\n",
    "                else:\n",
    "                    nums[lf + 1] += nums[lf]\n",
    "                    lf += 1\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int]) -> int:\n",
    "        left, right=0,len(nums)-1\n",
    "        ans = 0\n",
    "        while left<right:\n",
    "            if nums[left] == nums[right]:\n",
    "                left+=1 \n",
    "                right-=1\n",
    "            elif nums[left]<nums[right]:\n",
    "                nums[left+1]+=nums[left]\n",
    "                ans+=1\n",
    "                left+=1\n",
    "            else:\n",
    "                nums[right-1]+=nums[right]\n",
    "                ans+=1\n",
    "                right-=1\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
